home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / prio / _bin_heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  4.4 KB  |  225 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _bin_heap.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/impl/bin_heap.h>
  18.  
  19. //------------------------------------------------------------------------------
  20. // bin_heap: binary heaps  
  21. //           (compressed representation with array doubling)
  22. //
  23. // S. Naeher (1993)
  24. //
  25. //------------------------------------------------------------------------------
  26.  
  27.  
  28.  
  29. #define KEY(i)   (HEAP[i]->key)
  30. #define INF(i)   (HEAP[i]->inf)
  31.  
  32.  
  33. bin_heap::bin_heap(int n)  
  34. { if (n <= 0) 
  35.      error_handler(1,string("bin_heap constructor: illegal size = %d",n));
  36.   HEAP = new bin_heap_item[n];
  37.   for(int i = 0; i < n; i++) HEAP[i] = nil;
  38.   count = 0; 
  39.   max_size = n-2;  // sometimes we use HEAP[0], HEAP[count+1] as stoppers
  40. }
  41.  
  42. bin_heap::bin_heap(const bin_heap& H)
  43. { max_size = H.max_size;
  44.   count = H.count; 
  45.   HEAP = new bin_heap_item[max_size+2];
  46.   for(int i = 1; i <= count; i++) 
  47.   { HEAP[i] = new bin_heap_elem(H.HEAP[i]->key, H.HEAP[i]->inf,i);
  48.     H.copy_key(HEAP[i]->key);
  49.     H.copy_inf(HEAP[i]->inf);
  50.   }
  51. }
  52.  
  53. bin_heap& bin_heap::operator=(const bin_heap& H)
  54. { clear();
  55.   delete HEAP;
  56.   max_size = H.max_size;
  57.   count = H.count; 
  58.   HEAP = new bin_heap_item[max_size+2];
  59.   for(int i = 1; i <= count; i++) 
  60.   { HEAP[i] = new bin_heap_elem(H.HEAP[i]->key, H.HEAP[i]->inf,i);
  61.     copy_key(HEAP[i]->key);
  62.     copy_inf(HEAP[i]->inf);
  63.   }
  64.   return *this;
  65. }
  66.  
  67. bin_heap::~bin_heap()  
  68. { clear();
  69.   delete HEAP; 
  70. }
  71.  
  72. void bin_heap::clear()
  73. { for(int i=1; i <= count; i++) 
  74.   { clear_key(KEY(i));
  75.     clear_inf(INF(i));
  76.     delete HEAP[i];
  77.    }
  78.   count = 0;
  79. }
  80.  
  81.  
  82. void bin_heap::rise(int pos, bin_heap_item it)
  83. { 
  84.   HEAP[0] = it;  // use "it" as stopper
  85.  
  86.   register int  pi = pos/2;                     // parent index
  87.   register bin_heap_item parent = HEAP[pi];     // parent node
  88.  
  89.  
  90.   if (int_type())
  91.      while(parent->key > it->key)
  92.      { HEAP[pos] = parent;
  93.        parent->index = pos;
  94.        pos = pi;
  95.        pi >>= 1;
  96.        parent = HEAP[pi];
  97.       }
  98.   else
  99.      while (cmp(parent->key,it->key) > 0)
  100.      { HEAP[pos] = parent;
  101.        parent->index = pos;
  102.        pos = pi;
  103.        pi >>= 1;
  104.        parent = HEAP[pi];
  105.       }
  106.  
  107.   HEAP[pos] = it;
  108.   it->index = pos;
  109. }
  110.  
  111.  
  112. void bin_heap::sink(int pos, bin_heap_item it)
  113. { 
  114.   register int ci = 2*pos;       // child index
  115.  
  116.   register bin_heap_item child;  // child node
  117.  
  118.  
  119.   HEAP[count+1] = HEAP[count];   // stopper
  120.  
  121.   if (int_type())
  122.      while (ci <= count)
  123.      { child = HEAP[ci];
  124.        if (KEY(ci+1) < child->key) child = HEAP[++ci];
  125.        if (it->key > child->key) 
  126.        { HEAP[pos] = child;
  127.          child->index = pos;
  128.          pos = ci;
  129.          ci <<= 1;
  130.         }
  131.        else break;
  132.       }
  133.   else
  134.      while (ci <= count)
  135.      { child = HEAP[ci];
  136.        if (ci < count && cmp(KEY(ci+1),child->key) < 0) child = HEAP[++ci];
  137.        if (cmp(it->key,child->key)>0) 
  138.        { HEAP[pos] = child;
  139.          child->index = pos;
  140.          pos = ci;
  141.          ci <<= 1;
  142.         }
  143.        else break;
  144.       }
  145.  
  146.   HEAP[pos] =it;
  147.   it->index = pos;
  148. }
  149.  
  150.  
  151.  
  152. void bin_heap::decrease_key(bin_heap_item it, GenPtr k)
  153. { if (cmp(it->key,k)<0) 
  154.        error_handler(1,"bin_heap: key too large in decrease_key");
  155.   clear_key(it->key);
  156.   copy_key(k);
  157.   it->key = k;
  158.   rise(it->index, it);
  159. }
  160.  
  161.  
  162. bin_heap_item bin_heap::insert(GenPtr k, GenPtr i) 
  163. { 
  164.   bin_heap_item* H;
  165.  
  166.   if (count == max_size)  // resize
  167.   { // max_size *= 2;     // double array
  168.     max_size += 1024;
  169.     H = new bin_heap_item[max_size+2];
  170.     for(int i=1; i<= count; i++) H[i] = HEAP[i];
  171.     delete HEAP;
  172.     HEAP = H;
  173.    }
  174.  
  175.   count++;
  176.   copy_key(k);
  177.   copy_inf(i);
  178.   bin_heap_item it = new bin_heap_elem(k,i,count);
  179.   rise(count,it);
  180.  
  181.   return it;
  182. }
  183.  
  184.  
  185.  
  186.  
  187. void bin_heap::del_item(bin_heap_item it)
  188. { bin_heap_item p = HEAP[count];
  189.  
  190.   HEAP[count] = nil;
  191.  
  192.   count--;
  193.  
  194.   if (it != p)
  195.   { if (cmp(p->key,it->key) > 0)
  196.        sink(it->index, p);
  197.     else
  198.        rise(it->index, p);
  199.    }
  200.  
  201.   clear_key(it->key);
  202.   clear_inf(it->inf);
  203.  
  204.   delete it;
  205. }
  206.  
  207.  
  208. void bin_heap::change_inf(bin_heap_item it, GenPtr i) 
  209. { clear_inf(it->inf);
  210.   copy_inf(i);
  211.   it->inf = i; 
  212.  }
  213.  
  214. void bin_heap::print()
  215. { cout << "size = " << count << endl;
  216.   for(int i=1;i<=count;i++) 
  217.   { print_key(KEY(i));
  218.     cout << "-";
  219.     print_inf(INF(i));
  220.     cout << "  ";
  221.    }
  222.   newline;
  223. }
  224.  
  225.